// 131. 分割回文串
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.List;

public class Solution131 {
    List<List<String>> result = new ArrayList<>();

    public List<List<String>> partition(String s) {
        int length = s.length();

        // dp[i][j] 表示 s[i~j] 是否回文
        boolean[][] dp = new boolean[length][length];

        for (int i = 0; i < length; i++)
            dp[i][i] = true;

        for (int len = 1; len < length; len++) {
            for (int i = 0; i < length - len; i++) {
                if (len == 1 && s.charAt(i) == s.charAt(i + len)) {
                    dp[i][i + len] = true;
                    continue;
                }
                if (s.charAt(i) == s.charAt(i + len))
                    dp[i][i + len] = dp[i + 1][i + len - 1];
            }
        }

        for (int i = 0; i < length; i++)
            for (int j = 0; j < length; j++)
                System.out.println(dp[i][j]);

        backTrace(s, 0, dp, new ArrayList<String>());

        return result;
    }

    private void backTrace(String s, int cur, boolean[][] dp, List<String> list) {
        if (cur == s.length()) {
            result.add(new ArrayList<>(list));
        }

        if (cur > s.length())
            return;

        for (int i = cur; i < s.length(); i++) {
            if (dp[cur][i] == true) {
                list.add(s.substring(cur, i + 1));
                backTrace(s, i + 1, dp, list);
                list.remove(list.size() - 1);
            }
        }
    }
}
